from itertools import count, izip, islice

def partition_gen():
    d = dict()
    d[0] = 1
    
    for n in count(1):
        pn = 0
        sign = 1
        for k in xrange(1, n + 1):
            i = n - k*(3*k - 1)/2
            if i < 0: break
            pn += sign * d[i]
            j = n - k*(3*k + 1)/2
            if j < 0: break
            pn += sign * d[j]
            sign = -sign
        d[n] = pn % 1000000
        yield pn

def solution():
    for n,pn in izip(count(1), partition_gen()):
        if 0 == pn % 1000000:
            print n, pn
            break
            
from timeit import Timer
print Timer('solution()', 'from __main__ import solution').timeit(1)

            
